﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Compilex.Automata;
using Infraestruturex.BaseLibrary;

namespace Infraestruturex.Automata
{
    
    public class NFAConverter
    {
        class DFAConversionState
        {
            public DFAConversionState(HashSet<NFAState> nfaStates)
            {
                this.nfaStates = nfaStates;
                StringBuilder nameBuilder = new StringBuilder().Append("{");
                nfaStates.ForEach(state => nameBuilder.AppendFormat("{0}, ", state.Name));
                dfaState.Name = nameBuilder.ToString(0, nameBuilder.Length - 2) + "}";

            }
            public override string ToString()
            {
                return dfaState.Name;
            }
            public DFAState dfaState = new DFAState();
            public HashSet<NFAState> nfaStates = new HashSet<NFAState>();
            public bool isMarked = false;
        }

        public NFA NFA { get; private set; }

        private DFAConversionState startState;
        private NFAState[] nfaStates;
        private HashSet<string> alphabet;
        private HashSet<DFAConversionState> S_dfa = new HashSet<DFAConversionState>();

        public NFAConverter(NFA nfa)
        {
            this.NFA = nfa;
            this.nfaStates = nfa.GetStates();
            this.alphabet = GetAlphabet();
        }

        public DFA ConvertToDFA()
        {
            // S_dfa = {}
            // Add e-closure to S_dfa as the start state
            // Set the only state in S_dfa to "unmarked"
            startState = new DFAConversionState(new HashSet<NFAState>(
                NFA.StartState.GetEpsilonClosure()));

            S_dfa.Add(startState);
            while (StillUnmarkedStates())
            {
                DFAConversionState unmarkedState = GetFirstUnmarkedState();
                unmarkedState.isMarked = true;
                foreach (string symbol in alphabet)
                {
                    HashSet<NFAState> destinationStates = new HashSet<NFAState>(
                        GetEpsilonClosure(GetDestinationStates(unmarkedState.nfaStates, symbol)));

                    if (destinationStates.Count > 0)
                    {
                        DFAConversionState newState;
                        if (!HaveNfaStatesBeenAdded(destinationStates))
                        {
                            newState = new DFAConversionState(destinationStates);
                            S_dfa.Add(newState);
                        }
                        else
                        {
                            newState = S_dfa.Where(s => s.nfaStates.SetEquals(destinationStates)).First();
                        }

                        unmarkedState.dfaState.AddTransition(symbol, newState.dfaState);
                    }
                }
            }

            return GetDFA();

        }

        private DFA GetDFA()
        {
            DFA dfa = new DFA(startState.dfaState);
            S_dfa.Where(s => s.nfaStates.Where(n => n.IsAcceptState).Count() > 0).ForEach(
                s => s.dfaState.IsAcceptState = true);
            return dfa;
        }

        private bool HaveNfaStatesBeenAdded(HashSet<NFAState> state)
        {
            return S_dfa.Where(s => s.nfaStates.SetEquals(state)).Count() > 0;
        }

        private IEnumerable<NFAState> GetEpsilonClosure(HashSet<NFAState> states)
        {
            HashSet<NFAState> closure = new HashSet<NFAState>();
            states.ForEach(state => closure.UnionWith(state.GetEpsilonClosure()));
            return closure;
        }

        private HashSet<NFAState> GetDestinationStates(HashSet<NFAState> states, string symbol)
        {
            HashSet<NFAState> destinations = new HashSet<NFAState>();
            states.ForEach(state => destinations.UnionWith(state.GetDestinationStates(symbol)));
            return destinations;
        }

        private DFAConversionState GetFirstUnmarkedState()
        {
            return S_dfa.Where(state => !state.isMarked).First();
        }

        private bool StillUnmarkedStates()
        {
            return S_dfa.Where(state => !state.isMarked).Count() > 0;
        }


        private HashSet<string> GetAlphabet()
        {
            HashSet<string> alphabet = new HashSet<string>();
            foreach (NFAState state in nfaStates)
            {
                for(int i = 0; i < state.Transitions.Count; i++)
                {
                    ITransitionRule<NFAState> transition = state.Transitions[i];
                    if (transition is SimpleTransitionRule<NFAState>)
                    {
                        SimpleTransitionRule<NFAState> simpleTransition = 
                            (SimpleTransitionRule<NFAState>) transition;
                        alphabet.Add(simpleTransition.Input);
                    }
                }
            }
            return alphabet;
        }
    }
}